package com.ryujung.binary_tree.leetCode_111;

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ",\n left=" + left +
                ",\n right=" + right +
                '}';
    }
}

class Solution {
    /**
     * 很容易写错
     * 要注意，叶子节点必须是左右子树均为空的才是叶子节点
     * 所以在进行递归操作是，需要对root的状态分类：
     * - root为空：返回0
     * - root左右子树均为空：返回1
     * - root左右子树均不为空： 返回 左子树最小深度和右子树最小深度，其中的最小值+ 1
     * - root左子树或右子树为空：返回不为空的子树的最小树深度 + 1
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 为叶子结点，返回1
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 左右子树均不为空，返回左右子树的最小数深度
        if (root.left != null && root.right != null) {
            int leftDepth = minDepth(root.left);
            int rightDepth = minDepth(root.right);
            int minDepth = Math.min(leftDepth, rightDepth) + 1;
            return minDepth;
        }
        // 仅有左子树或右子树一方为空，返回不为空的子树的最小深度。
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }

        return minDepth(root.left) + 1;
    }
    // 时间复杂度：O(n) 需要遍历二叉树
    // 空间复杂度：O(height) 递归需要的栈空间，取决于树的高度

    // BFS
    public int minDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> que = new ArrayDeque<>();
        que.add(root);
        int depth = 0;

        while (!que.isEmpty()) {
            depth++;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                if(node.left==null && node.right==null){
                    return depth;
                }
                if(node.left!=null){
                    que.add(node.left);
                }
                if(node.right!=null){
                    que.add(node.right);
                }
            }
        }
        return depth;
    }
    // 时间复杂度：O(n) 遍历二叉树
    // 空间复杂度：O(n) 需要队列存放二叉树的节点，最坏情况所需空间接近n

}